#include <iostream>
#include <fstream>
#include <vector>
#include <cassert>
using namespace std;

typedef int keytype;

int bisearch(vector<keytype> &keys, int k, int low, int high)
{
  int mid;

  while (low <= high){
    mid = (low + high)/2;
    if (k > keys[mid])
      low = mid + 1;
    else
      high = mid - 1;
  }
  return low;
}

void twoway_insert(vector<keytype> &keys, vector<keytype> &nk, int &first, int &final)
{
  int i, j, loc;

  first = final = 0;
  if (keys.size() == 0)
    return;
  nk.resize(keys.size());
  nk[0] = keys[0];
  for (i = 1; i < keys.size(); i++){
    if (keys[i] > nk[0]){
      if (final == 0){
	final = 1;
	nk[final] = keys[i];
      }
      else{
	loc = bisearch(nk, keys[i], 0, final);
	for (j = final; j >= loc; j--)
	  nk[j+1] = nk[j];
	nk[j+1] = keys[i];
	final++;
      }	
    }
    else{
      if (first == 0){
	first = nk.size()-1;
	nk[first] = keys[i];
      }
      else{
	loc = bisearch(nk, keys[i], first, nk.size()-1);
	for (j = first; j < loc; j++)
	  nk[j-1] = nk[j];
	nk[j-1] = keys[i];
	first--;
      }
    }
  }
}

void print(vector<keytype> &keys, int first, int final)
{
  if (keys.size() == 0)
    return;
  for (int i = first; i != final; i = (i+1)%keys.size())
    cout << keys[i] << "\t";
  cout << keys[final] << endl;
}

int main()
{
  ifstream in("sort.txt");
  vector<keytype> keys, nk;
  int first, final;
  keytype k;

  assert(in);
  while (in >> k)
    keys.push_back(k);

  twoway_insert(keys, nk, first, final);
  print(nk, first, final);
  in.close();

  return 0;
}
